home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / prolog / brklyprl.lha / Emulator / mark_copy.h < prev    next >
Encoding:
C/C++ Source or Header  |  1989-04-14  |  5.8 KB  |  257 lines
  1.  
  2. /* Copyright (C) 1988, 1989 Herve' Touati, Aquarius Project, UC Berkeley */
  3.  
  4. /* Copyright Herve' Touati, Aquarius Project, UC Berkeley */
  5.  
  6. extern void mark_from_base(Cell*);
  7. extern void mark_from_base_sweep(Cell*);
  8. extern void copy_from_base(Cell*);
  9.  
  10. struct UpStack {
  11.   Cell* sp;
  12.   Cell* sp0;
  13.   void init(Cell* p) {sp0 = sp = p;}
  14.   Cell* bottom() {return sp0;}
  15.   Cell* top() {return sp;}
  16.   void push(Cell* val) {*sp++ = cell(val);}
  17.   Cell* pop() {return cellp(*--sp);}
  18.   int nonempty() {return (sp > sp0);}
  19. };
  20.  
  21. struct DownStack {
  22.   Cell* sp;
  23.   Cell* sp0;
  24.   void init(Cell* p) {sp0 = sp = p;}
  25.   Cell* bottom() {return sp0;}
  26.   Cell* top() {return sp;}
  27.   void push(Cell* val) {*sp-- = cell(val);}
  28.   Cell* pop() {return cellp(*++sp);}
  29.   int nonempty() {return (sp < sp0);}
  30. };
  31.  
  32.  /* basic data structure to implement Cheney's copy algorithm */
  33. struct CopyStack {
  34.   Cell* first;
  35.   Cell* second;
  36.   void init(Cell* p) {first = second = p;}
  37.   Cell* top() {return first;}
  38.   void push(Cell val) {*first++ = val;}
  39.   Cell* pop() {return second++;}
  40.   int nonempty() {return (first > second);}
  41. };
  42.  
  43. inline Cell* max(Cell* a, Cell* b)
  44. {
  45.   return (a > b) ? a : b;
  46. }
  47.  
  48. inline Cell* min(Cell* a, Cell* b)
  49. {
  50.   return (a < b) ? a : b;
  51. }
  52.  
  53. extern void init_stats();
  54. extern void display_stat1(char*, int, int);
  55. extern void init_marking_table();
  56. extern CellPtr B2, HMIDDLE;
  57. extern unsigned char MARK;
  58.  
  59.  /* UTILITIES */
  60.  
  61. inline int to_new_space(Cell* p)
  62. { return (p < H) && (p >= HMIN); }
  63.  
  64. inline int pointer_to_new(Cell val)
  65. { return (get_tag(val) != TAGCONST && to_new_space(addr(val))); }
  66.  
  67.  /* better be sure p points to new space */
  68. inline Cell* reloc_addr(Cell* p)
  69. { return cellp(*p); }
  70.  
  71. inline void set_reloc_addr(Cell* p, Cell* new_addr)
  72. { *p = cell(new_addr); }
  73.  
  74. inline Cell check_and_relocate(Cell var)
  75. {
  76.   int tag = get_tag(var);
  77.   Cell* ptr = addr(var);
  78.   if (tag != TAGCONST && to_new_space(ptr))
  79.     return make_ptr(tag, reloc_addr(ptr));
  80.   else
  81.     return var;
  82. }
  83.  
  84.  /* suppose that p is an address to a location in new space */
  85.  /* please do the check!! note: new space contain a relocation table. */
  86. overload relocate;
  87. inline Cell relocate(Cell var)
  88. { return make_ptr(get_tag(var), reloc_addr(addr(var))); }
  89.  
  90. inline Cell relocate(int tag, Cell* p)
  91. { return make_ptr(tag, reloc_addr(p)); }
  92.  
  93. inline void mark(Cell* p)
  94. { MKMIN[p - HMIN] = MARK; }
  95.  
  96. inline int marked(Cell* p)
  97. { return (MKMIN[p - HMIN] == MARK); }
  98.  
  99. inline int unmarked(Cell* p)
  100. { return (MKMIN[p - HMIN] != MARK); }
  101.  
  102. extern void store_regs_in_env();
  103. extern void restore_top_env();
  104.  
  105. struct Env {
  106.   Cell* e;
  107.   int size;
  108.   int already_treated;
  109.   void next() {
  110.     size = instrp(e[P_ENV_OFFSET])->arg2; /* P points to the call instr */
  111.     already_treated = 0;
  112.     e = cellp(e[E_ENV_OFFSET]);
  113.   }
  114.   Env() {}
  115.   Env(Cell* E) {init(E);}
  116.   void init(Cell* E) {
  117.     e = E;
  118.     next();
  119.   }
  120.   void treated(int n) {already_treated = n;}
  121.   void mark();
  122.   void fast_copy();
  123.   void mark_sweep();
  124.   void update();
  125. };
  126.  
  127. struct ChoiceRecord {
  128.   Cell* tr;
  129.   Cell* e;
  130.   Cell* h;
  131. };
  132.  
  133. struct Choice {
  134.   Cell* b;
  135.   Env already_done;
  136.   Env preserved;
  137.   Cell* tr;
  138.   Choice(Cell*, Cell*);
  139.   void next() {
  140.     b = b + FIXED_CP_SIZE + b[SIZE_CP_OFFSET];
  141.     preserved.init(cellp(b[E_CP_OFFSET]));
  142.   }
  143.   int last() { return (b >= B2); }
  144.   void mark();
  145.   void mark_sweep();
  146.   void virtual_backtrack();
  147.   void virtual_backtrack_sweep();
  148.   void mark_preserved_envs();
  149.   void mark_preserved_envs_sweep();
  150.   void update();
  151.   void update_preserved_envs();
  152. };
  153.  
  154. extern void cp_to_cp_forward();
  155. extern void cp_to_cp_backward();
  156.  
  157.  /* The TRAIL STACK */
  158.  
  159. enum {
  160.   TRAIL_SKIP,
  161.   TRAIL_KEEP,
  162.   TRAIL_RELOC,
  163.   TRAIL_IND_RELOC,
  164.   TRAIL_COPY_RELOC,
  165.   TRAIL_MARK
  166.   };
  167.  
  168.  /* sort of a cp cache, with some control info. */
  169.  /* the main point is to make sure that the TR entries are updated */
  170.  /* after the former values are read */
  171. struct TrailCP {
  172.   Cell* b;
  173.   Cell* next_b;
  174.   Cell* last_b;
  175.   Cell* tr;
  176.   Cell* next_tr;
  177.   Cell* e;
  178.   Cell* h;
  179.   TrailCP(Cell* B2, Cell* B) {b = B2; last_b = B; init();}
  180.   int nonempty() {return (b > last_b);}
  181.   void init() {next_b = b; 
  182.            next_tr = cellp(b[TR_CP_OFFSET]);
  183.            next();}
  184.   void next() {b = next_b;
  185.            e = cellp(b[E_CP_OFFSET]);
  186.            h = cellp(b[H_CP_OFFSET]);
  187.            tr = next_tr;
  188.            next_b = b - (FIXED_CP_SIZE + b[SIZE_CP_OFFSET]);
  189.            next_tr = cellp(next_b[TR_CP_OFFSET]);}
  190.   void update_tr(Cell* tr) { next_b[TR_CP_OFFSET] = cell(tr); }
  191.   int pass1_action(Cell* ptr) {
  192.     if (ptr >= e || (ptr < E0 && ptr >= h)) 
  193.       return TRAIL_SKIP;
  194.     else if (ptr >= E2 || (ptr < E0 && ptr >= HMIN))
  195.       return TRAIL_KEEP;
  196.     else
  197.       return (pointer_to_new(*ptr)) ? TRAIL_MARK : TRAIL_KEEP;
  198.   }
  199.   int pass2_action(Cell* ptr) {
  200. #ifdef WITH_VIRTUAL_BACK
  201.     if (*ptr == make_ptr(TAGREF,ptr)) 
  202.       return TRAIL_SKIP;
  203.     else if (to_new_space(ptr)) {
  204. #else
  205.     if (to_new_space(ptr)) {
  206. #endif
  207.       if (unmarked(ptr))
  208.     return TRAIL_SKIP;
  209.       else
  210.     return (ptr >= HMIDDLE) ? TRAIL_RELOC : TRAIL_COPY_RELOC;
  211.     } else 
  212.       return TRAIL_IND_RELOC;
  213.   }
  214.   int pass2_action_sweep(Cell* ptr) {
  215. #ifdef WITH_VIRTUAL_BACK
  216.     if (*ptr == make_ptr(TAGREF,ptr)) 
  217.       return TRAIL_SKIP;
  218.     else if (to_new_space(ptr)) {
  219. #else
  220.     if (to_new_space(ptr)) {
  221. #endif
  222.       if (unmarked(ptr))
  223.     return TRAIL_SKIP;
  224.       else
  225.     return TRAIL_RELOC;
  226.     } else 
  227.       return TRAIL_IND_RELOC;
  228.   }
  229. };
  230.  
  231. extern void gccontrol_pass2();
  232.  
  233. enum {
  234.   SHOULD_COPY,
  235.   SHOULD_MARK,
  236.   SHOULD_CHECK_MARK,
  237.   SHOULD_RELOC,
  238.   SHOULD_NEITHER,
  239.   SHOULD_LEAVE
  240.   };
  241.  
  242. extern void mark_compact();
  243. extern void fast_copy();
  244. extern struct rusage gc_rusage;
  245. extern int getrusage(...);
  246. extern CellPtr H_entry_value;
  247. extern CellPtr H2_entry_value;
  248. extern CellPtr TR_entry_value;
  249. extern CellPtr TR2_entry_value;
  250.  
  251. extern void gc_init();
  252. extern void global_sweep();
  253. extern void restore_cps();
  254. extern ChoiceRecord SAVED_CP;
  255. extern void gctrail_pass11();
  256. extern void compute_stats();
  257.